package com.example.origin.demo.suanfa.leecode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 *     1
 *    / \
 *   2   3
 *  / \   \
 * 4   5   6
 *    / \
 *   7   8
 *
 * 前序遍历（根节点 → 左子树 → 右子树）
 * 表达式树求值：在计算机科学中，前序遍历常用于表示和处理表达式树。例如，对于一个表示算术表达式的二叉树，前序遍历的结果正好对应于表达式的前缀表示（波兰表示法），可以直接进行求值。
 *
 * 复制/克隆二叉树：若要复制一棵二叉树，可以使用前序遍历来依次创建新节点，并按照遍历顺序连接它们。
 *
 * 打印目录结构：在文件系统中，目录结构可以看作是二叉树（每个目录节点有两个子节点，分别代表子目录和文件列表）。前序遍历可以用来按照“目录名 → 子目录 → 文件”的顺序打印目录结构。
 *
 * 后序遍历（左子树 → 右子树 → 根节点）
 * 计算二叉树的大小/高度：后序遍历可用于计算二叉树的大小（节点总数）或高度。在遍历过程中，每当访问到一个叶节点（没有子节点的节点）时，计数器加一；当访问到一个非叶节点时，更新当前最大深度。
 *
 * 计算二叉树的节点值之和：对于每个节点，其子树的节点值之和可以通过后序遍历计算得出。在遍历过程中，每当访问到一个叶节点时，累加其值；当访问到一个非叶节点时，将其子树的节点值之和与其自身的值相加。
 *
 * 释放二叉树资源：如果二叉树的节点包含需要释放的资源（如文件句柄、数据库连接等），可以使用后序遍历来确保先释放子节点的资源，再释放当前节点的资源。
 */
public class No144BinaryTreePreorderTraversal {
    public static void main(String[] args) {
        // 创建根节点
        TreeNode root = new TreeNode(1);

        // 创建根节点的左右子节点
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);

        // 继续创建左子树的子节点
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.left.right.left = new TreeNode(7);
        root.left.right.right = new TreeNode(8);

        // 创建右子树的子节点
        root.right.right = new TreeNode(6);

        List<Integer> integers = preorderTraversal(root);
        for (int i = 0; i < integers.size(); i++) {
            System.out.print(integers.get(i));
        }
        System.out.println();
        integers = preorderTraversal2(root);
        for (int i = 0; i < integers.size(); i++) {
            System.out.print(integers.get(i));
        }
        System.out.println();

        integers = postorderTraversal(root);
        for (int i = 0; i < integers.size(); i++) {
            System.out.print(integers.get(i));
        }
        System.out.println();


        integers = postorderTraversal2(root);
        for (int i = 0; i < integers.size(); i++) {
            System.out.print(integers.get(i));
        }
        System.out.println();



    }

    static class TreeNode {

        Integer val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }

    }


    public static List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        inorderRecursive(root, result);
        return result;
    }

    private static void inorderRecursive(TreeNode node, List<Integer> list) {
        if (node == null) {
            return;
        }
        // 访问当前节点
        list.add(node.val);

        // 先遍历左子树
        inorderRecursive(node.left, list);

        // 再遍历右子树
        inorderRecursive(node.right, list);
    }

    /**
     * 前序遍历二叉树
     * @param root
     * @return
     */
//    public static List<Integer> preorderTraversal2(TreeNode root) {
//        Stack<TreeNode> stack = new Stack<>();
//        List<Integer> result = new ArrayList<>();
//        TreeNode curr = root;
//
//        while (curr != null || !stack.isEmpty()) {
//            while (curr != null) {
//                // 访问当前节点
//                result.add(curr.val);
//
//                // 将右子节点先入栈，确保后续按左→根→右顺序访问
//                stack.push(curr.right);
//
//                curr = curr.left;
//            }
//
//            // 若栈不为空，弹出栈顶节点作为当前节点
//            curr = stack.pop();
//        }
//
//        return result;
//    }

    public static List<Integer> preorderTraversal2(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        List<Integer> list = new ArrayList<>();
        TreeNode curr = root;

        while (!stack.isEmpty()||curr!=null){
            while (curr!=null){
                list.add(curr.val);
                stack.push(curr.right);
                curr = curr.left;
            }
            curr = stack.pop();
        }


        return list;
    }

    /**
     * 后序遍历二叉树
     * @param root
     * @return
     */
    public static List<Integer> postorderTraversal(TreeNode root) {
        Stack<TreeNode> stack1 = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();
        List<Integer> result = new ArrayList<>();

        if (root != null) {
            stack1.push(root);
        }

        while (!stack1.isEmpty()) {
            TreeNode node = stack1.pop();
            stack2.push(node); // 将当前节点暂时放入第二个栈

            if (node.left != null) {
                stack1.push(node.left);
            }
            if (node.right != null) {
                stack1.push(node.right);
            }
        }

        // 从第二个栈中按后序遍历顺序取出节点值
        while (!stack2.isEmpty()) {
            TreeNode node = stack2.pop();
            result.add(node.val);
        }

        return result;
    }

    public static List<Integer> postorderTraversal2(TreeNode root) {
        Stack<TreeNode> stack1 = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();
        List<Integer> list = new ArrayList<>();

        if (root!=null){
            stack1.push(root);
        }
        while (!stack1.isEmpty()){
            TreeNode node = stack1.pop();
            stack2.push(node);
            if (node.left!=null) {
                stack1.push(node.left);
            }
            if (node.right!=null) {
                stack1.push(node.right);
            }
        }
        while (!stack2.isEmpty()){
            list.add(stack2.pop().val);
        }
        return list;
    }

}
